/*
 * @lc app=leetcode.cn id=1588 lang=cpp
 *
 * [1588] 所有奇数长度子数组的和
 */

// @lc code=start
class Solution
{
public:
  int sumOddLengthSubarrays(vector<int>& arr)
  {
    int n = arr.size();
    vector<int> prefix_sum(n + 1);
    for (int i = 1; i <= n; ++i)
      prefix_sum[i] = arr[i - 1] + prefix_sum[i - 1];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i - 1; j >= 0; j -= 2)
        ans += prefix_sum[i] - prefix_sum[j];
    }
    return ans;
  }
};
// @lc code=end
